{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #括号生成"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: generateParenthesis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #括号生成"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>正整数&nbsp;<code>n</code>&nbsp;代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 <strong>有效的 </strong>括号组合。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>[&quot;((()))&quot;,&quot;(()())&quot;,&quot;(())()&quot;,&quot;()(())&quot;,&quot;()()()&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>[&quot;()&quot;]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 8</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 22&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/generate-parentheses/\">https://leetcode-cn.com/problems/generate-parentheses/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [IDBivT](https://leetcode.cn/problems/IDBivT/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [IDBivT](https://leetcode.cn/problems/IDBivT/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 回溯算法-框架\n",
    "# 1、一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。\n",
    "\n",
    "# 2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。\n",
    "\n",
    "# 对于 2n 个位置，必然有 n 个左括号，n 个右括号，所以我们不是简单的记录穷举位置 i，而是用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/bao-li-sou-96f79/hui-su-sua-89170/\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = [] # 路径\n",
    "        self.track = '' # 路径列表\n",
    "\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        # 边界条件\n",
    "        if n == 0:\n",
    "            return\n",
    "\n",
    "        # res = []\n",
    "        # track = ''\n",
    "        # 第一个n:还剩多少个左括号，第二个n:还剩多少个右括号\n",
    "        self.backtrack(n, n) # 里面应该传参：路径，路径列表。但这里这两个参数已经定义为全局变量，所以这里传2个n，分别表示还剩下多少个left，还剩下多少个right没有使用\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, left, right):\n",
    "        # 剪枝\n",
    "        if right < left: # 右括号剩下的更多，不正常\n",
    "            return\n",
    "        if left < 0 or right < 0:\n",
    "            return\n",
    "        # 终止条件\n",
    "        if left ==0 and right == 0:\n",
    "            self.res.append(self.track)\n",
    "            return\n",
    "        \n",
    "        # 选择列表的循环：\n",
    "        # for c in [\"(\", \")\"]:\n",
    "\n",
    "        # 做选择（先尝试选左括号）\n",
    "        self.track += \"(\"\n",
    "        # 递归\n",
    "        self.backtrack(left-1, right)\n",
    "        # 撤销选择\n",
    "        self.track = self.track[:-1]\n",
    "\n",
    "        # 做选择（再尝试选右括号）\n",
    "        self.track += \")\"\n",
    "        # 递归\n",
    "        self.backtrack(left, right-1)\n",
    "        # 撤销选择\n",
    "        self.track = self.track[:-1]\n",
    "\n",
    "\n",
    "# labuladong\n",
    "\n",
    "# from typing import List\n",
    "\n",
    "# def generateParenthesis(n: int) -> List[str]:\n",
    "#     if n == 0: \n",
    "#         return []\n",
    "#     # 记录所有合法的括号组合\n",
    "#     res = []\n",
    "#     # 回溯过程中的路径\n",
    "#     track = ''\n",
    "#     # 可用的左括号和右括号数量初始化为 n\n",
    "#     backtrack(n, n, track, res)\n",
    "#     return res\n",
    "\n",
    "# # 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个\n",
    "# def backtrack(left: int, right: int, track: str, res: List[str]) -> None:\n",
    "#     # 若左括号剩下的多，说明不合法\n",
    "#     if right < left:\n",
    "#         return\n",
    "#     # 数量小于 0 肯定是不合法的\n",
    "#     if left < 0 or right < 0:\n",
    "#         return\n",
    "#     # 当所有括号都恰好用完时，得到一个合法的括号组合\n",
    "#     if left == 0 and right == 0:\n",
    "#         res.append(track)\n",
    "#         return\n",
    "    \n",
    "#     # 尝试放一个左括号\n",
    "#     track += '(' # 选择\n",
    "#     backtrack(left - 1, right, track, res)\n",
    "#     track = track[:-1] # 撤消选择\n",
    "\n",
    "#     # 尝试放一个右括号\n",
    "#     track += ')' # 选择\n",
    "#     backtrack(left, right - 1, track, res)\n",
    "#     track = track[:-1] # 撤消选择"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        less = ['']\n",
    "        for _ in range(n):\n",
    "            less = [a[:i]+'()'+a[i:] for a in less for i in range(len(less[0])+1)]\n",
    "            less = list(set(less))\n",
    "        return less"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        def helper(tmp):\n",
    "            if len(tmp) == n*2 and tmp.count(\"(\") == tmp.count(\")\"):\n",
    "                res.append(tmp)\n",
    "            if len(tmp) > n*2:\n",
    "                return\n",
    "            \n",
    "            helper(tmp + \"(\")\n",
    "            helper(tmp + \")\")\n",
    "        helper(\"\")\n",
    "\n",
    "        result = []\n",
    "        for node in res:\n",
    "            tmp = node\n",
    "            while tmp.find(\"()\") != -1:\n",
    "                tmp = tmp.replace(\"()\",\"\")\n",
    "            if tmp == \"\":\n",
    "                result.append(node)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        path = \"\"\n",
    "        res = []\n",
    "        def dfs(path, left, right):\n",
    "            if left > n or right > left:\n",
    "                return\n",
    "            if len(path) == 2*n:\n",
    "                res.append(path)\n",
    "            dfs(path+\"(\", left + 1, right)\n",
    "            dfs(path+\")\", left, right + 1)\n",
    "        dfs(path, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        path = [0]*2*n\n",
    "        def match_x(path):\n",
    "            list1 = []\n",
    "            for x in path:\n",
    "                if x==\"(\": list1.append(x)\n",
    "                else:\n",
    "                    try:\n",
    "                        list1.pop()\n",
    "                    except: return False\n",
    "            if len(list1)==0: return True\n",
    "            return False\n",
    "        def dfs(path,level,x):\n",
    "            path[level] = x\n",
    "            if level==2*n-1:\n",
    "                # print(path)\n",
    "                nonlocal ans\n",
    "                if match_x(path): ans.append(\"\".join(path))\n",
    "                return 0\n",
    "            for i in range(2):\n",
    "                x2 = \"(\" if i==0 else \")\"\n",
    "                dfs(path,level+1,x2)\n",
    "        dfs(path,0,\"(\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def cur(path,l:int, r:int):\n",
    "            if l>n or r>l:\n",
    "                return\n",
    "            if len(path)==n*2:\n",
    "                res.append(path)\n",
    "                return\n",
    "\n",
    "            cur(path+\"(\", l+1,r )\n",
    "            cur(path+\")\",l, r+1)\n",
    "\n",
    "        \n",
    "        res=[]\n",
    "        cur(\"\",0,0)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        cur_str = ''\n",
    "        def dfs(cur_str,left,right):\n",
    "            if left == 0 and right ==0:\n",
    "                res.append(cur_str)\n",
    "                return\n",
    "            if left>right:\n",
    "                return\n",
    "            if left>0:\n",
    "                dfs(cur_str+'(',left-1,right)\n",
    "            if right>0:\n",
    "                dfs(cur_str+')',left,right-1)\n",
    "        dfs(cur_str,n,n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "\n",
    "        def dfs(left, right, ll):\n",
    "            if right > left or left > n or right > n:\n",
    "                return\n",
    "            if left == n and right == n:\n",
    "                ans.append(''.join(ll))\n",
    "                return\n",
    "            if left >= right and left < n:\n",
    "                ll.append('(')\n",
    "                dfs(left + 1, right, ll)\n",
    "                ll.pop()\n",
    "            if right < left and left <= n:\n",
    "                ll.append(')')\n",
    "                dfs(left, right + 1, ll)\n",
    "                ll.pop()\n",
    "        \n",
    "        dfs(0, 0, [])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans, path = [], []\n",
    "        def dfs(l, r):\n",
    "            if l == 0 and r == 0:\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            if r >= l:\n",
    "                if l > 0:\n",
    "                    path.append('(')\n",
    "                    dfs(l - 1, r)\n",
    "                    path.pop()\n",
    "                if r > 0:\n",
    "                    path.append(')')\n",
    "                    dfs(l, r - 1)\n",
    "                    path.pop()\n",
    "        dfs(n, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        path = \"\"\n",
    "        res = []\n",
    "        def dfs(path, left, right):\n",
    "            if left > n or right > left:\n",
    "                return\n",
    "            if len(path) == 2*n:\n",
    "                res.append(path)\n",
    "            dfs(path+\"(\", left+1, right)\n",
    "            dfs(path+\")\", left, right+1)\n",
    "        dfs(path, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(item: str, left: int, right: int):\n",
    "            if left == 0 and right == 0:\n",
    "                # 左右括号用完\n",
    "                ans.append(item)\n",
    "                return\n",
    "            if left > 0:\n",
    "                # 左括号有剩\n",
    "                dfs(item + \"(\", left - 1, right)\n",
    "            if left < right:\n",
    "                # 已经增加的左括号多余右括号\n",
    "                dfs(item + \")\", left, right - 1)\n",
    "        ans = []\n",
    "        dfs(\"\", n, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        sub = []\n",
    "        tt = n * 2\n",
    "        def create(i, ln):\n",
    "            if i == tt:\n",
    "                ans.append(''.join(sub))\n",
    "                return\n",
    "            if ln < n:\n",
    "                sub.append('(')\n",
    "                create(i+1, ln + 1)\n",
    "                sub.pop()\n",
    "            if i - ln < ln:\n",
    "                sub.append(')')\n",
    "                create(i+1, ln)\n",
    "                sub.pop()\n",
    "                \n",
    "        create(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(left, right, path):\n",
    "            if left==n and right==n:\n",
    "                res.append(path)\n",
    "                return\n",
    "            if left<n:\n",
    "                dfs(left+1,right,path+'(')\n",
    "            if right<left:\n",
    "                dfs(left,right+1,path+')')\n",
    "        res = []\n",
    "        dfs(0,0,'')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def f(left, right, s):\n",
    "            if left == 0 and right == 0:\n",
    "                ans.append(s)\n",
    "            if left:\n",
    "                f(left - 1, right, s + '(')\n",
    "            if right > left:\n",
    "                f(left, right - 1, s + ')')\n",
    "        \n",
    "        f(n, n, '')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans, path = [], []\n",
    "\n",
    "        def process(r, d):\n",
    "            if d == n and r == 0:\n",
    "                ans.append(''.join(list(path)))\n",
    "                return\n",
    "\n",
    "            if r > 0:\n",
    "                path.append(')')\n",
    "                process(r - 1, d)\n",
    "                path.pop()\n",
    "\n",
    "            if d < n:\n",
    "                path.append(\"(\")\n",
    "                process(r + 1, d + 1)\n",
    "                path.pop()\n",
    "\n",
    "        process(0, 0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    print(s.generateParenthesis(3))\n",
    "    print(s.generateParenthesis(1))\n",
    "    print(s.generateParenthesis(2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(left, right, tmp):\n",
    "            if left < 0 or right < 0:\n",
    "                return\n",
    "            if len(tmp) == n * 2:\n",
    "                res.append(''.join(tmp))\n",
    "                return\n",
    "            tmp.append('(')\n",
    "            dfs(left - 1, right + 1, tmp)\n",
    "            tmp.pop()\n",
    "            tmp.append(')')\n",
    "            dfs(left, right - 1, tmp)\n",
    "            tmp.pop()\n",
    "        \n",
    "        res = []\n",
    "        dfs(n, 0, [])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 回溯算法-框架\n",
    "# 1、一个「合法」括号组合的左括号数量一定等于右括号数量，这个很好理解。\n",
    "\n",
    "# 2、对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。\n",
    "\n",
    "# 对于 2n 个位置，必然有 n 个左括号，n 个右括号，所以我们不是简单的记录穷举位置 i，而是用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = [] # 路径\n",
    "        self.track = '' # 路径列表\n",
    "\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 0:\n",
    "            return\n",
    "\n",
    "        # res = []\n",
    "        # track = ''\n",
    "        self.backtrack(n, n) # 里面应该传参：路径，路径列表。但这里这两个参数已经定义为全局变量，所以这里传2个n，分别表示还剩下多少个left，还剩下多少个right没有使用\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, left, right):\n",
    "        # 终止条件\n",
    "        if right < left: # 右括号剩下的更多，不正常\n",
    "            return\n",
    "        if left < 0 or right < 0:\n",
    "            return\n",
    "        if left ==0 and right == 0:\n",
    "            self.res.append(self.track)\n",
    "            return\n",
    "\n",
    "\n",
    "        # 做选择（先尝试选左括号）\n",
    "        self.track += \"(\"\n",
    "        # 递归\n",
    "        self.backtrack(left-1, right)\n",
    "        # 撤销选择\n",
    "        self.track = self.track[:-1]\n",
    "\n",
    "        # 做选择（再尝试选右括号）\n",
    "        self.track += \")\"\n",
    "        # 递归\n",
    "        self.backtrack(left, right-1)\n",
    "        # 撤销选择\n",
    "        self.track = self.track[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(seq, lcnt):\n",
    "            if len(seq) == 2 * n:\n",
    "                ans.append(seq[:])\n",
    "                return\n",
    "            \n",
    "            if lcnt < n:\n",
    "                dfs(seq + '(', lcnt + 1)\n",
    "            if len(seq) - lcnt < lcnt:\n",
    "                dfs(seq + ')', lcnt)\n",
    "        \n",
    "        ans = []\n",
    "        dfs(\"\", 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans=[]\n",
    "        def trace(s,left,right):\n",
    "            if len(s)==2*n:\n",
    "                ans.append(\"\".join(s))\n",
    "                return \n",
    "            if left < n :\n",
    "                s.append('(')\n",
    "                trace(s,left+1,right)\n",
    "                s.pop()\n",
    "            if right < left :\n",
    "                s.append(')')\n",
    "                trace(s,left,right+1)\n",
    "                s.pop()\n",
    "        trace([],0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        path=[]\n",
    "        if n<=0:\n",
    "            return []\n",
    "        def dfs(ans,left,right):\n",
    "            if left>n or right>left:\n",
    "                return \n",
    "            if len(ans)==n*2:\n",
    "                path.append(ans)\n",
    "                return\n",
    "            dfs(ans+'(',left+1,right)\n",
    "            dfs(ans+')',left,right+1)\n",
    "        dfs('',0,0)\n",
    "        return path\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        ans = []\n",
    "        path = [] \n",
    "        def dfs(i: int, open: int) -> None:\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if open < n:\n",
    "                path.append('(')\n",
    "                dfs(i + 1, open + 1)\n",
    "                path.pop()\n",
    "            if i - open < open:\n",
    "                path.append(')')\n",
    "                dfs(i + 1, open)\n",
    "                path.pop()\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 思路：\n",
    "# 定义generate,递归,长度为n的是由n-1的+（ 或者+）构成\n",
    "# def valid 每次加上（ or ），检验（的个数-）的个数<0,直接返回False\n",
    "# 判断(的个数 和 )的个数是否为0\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def generate(A):\n",
    "            if len(A)==2*n:\n",
    "                # 构造已完成\n",
    "                if valid(A):\n",
    "                    ans.append(''.join(A))\n",
    "            else:\n",
    "                # 继续构造\n",
    "                A.append('(')\n",
    "                generate(A)\n",
    "                A.pop()\n",
    "\n",
    "                A.append(')')\n",
    "                generate(A)\n",
    "                A.pop()\n",
    "\n",
    "        def valid(A):\n",
    "            tmp = 0\n",
    "            for i in A:\n",
    "                if i=='(':\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "                if tmp<0:\n",
    "                    return False\n",
    "            return tmp==0\n",
    "        \n",
    "        # 调用以上函数\n",
    "        ans = []\n",
    "        generate([])\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        self.str = \"\"\n",
    "        def dfs(i, left_num, right_num):\n",
    "            if i == 2*n:\n",
    "                ans.append(self.str)\n",
    "                return\n",
    "            if left_num < n:\n",
    "                self.str += \"(\"\n",
    "                dfs(i+1, left_num+1, right_num)\n",
    "                self.str = self.str[:-1]\n",
    "            if left_num-right_num > 0:\n",
    "                self.str += \")\"\n",
    "                dfs(i+1, left_num, right_num+1)\n",
    "                self.str = self.str[:-1]\n",
    "            return\n",
    "        dfs(0, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(l, r, path):\n",
    "            if len(path) == 2 * n:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if l > r:\n",
    "                path.append(')')\n",
    "                dfs(l, r + 1, path)\n",
    "                path.pop()\n",
    "            if l < n:\n",
    "                path.append('(')\n",
    "                dfs(l + 1, r, path)\n",
    "                path.pop()\n",
    "\n",
    "        ans = []\n",
    "        dfs(0, 0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        global_list = []\n",
    "        def gen(tmp, n_r, n_l, count):\n",
    "            if n_r == 0 and n_l == 0:\n",
    "                global_list.append(tmp)\n",
    "            elif n_r == 0:\n",
    "                return\n",
    "            elif n_l == 0:\n",
    "                global_list.append(tmp+n_r*\")\")\n",
    "            else:\n",
    "                if count>0:\n",
    "                    gen(tmp+')', n_r-1, n_l, count-1)\n",
    "                if count>=0:\n",
    "                    gen(tmp+'(', n_r, n_l-1, count+1)\n",
    "        gen('', n,n,0)\n",
    "        return global_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans,path = [],[]\n",
    "        def backtrack(l,r):\n",
    "            if l==n and r==n:\n",
    "                ans.append(''.join(path[:]))\n",
    "                return\n",
    "            if l<n:\n",
    "                path.append(\"(\")\n",
    "                backtrack(l+1,r)\n",
    "                path.pop()\n",
    "            if l>r:\n",
    "                path.append(')')\n",
    "                backtrack(l,r+1)\n",
    "                path.pop()\n",
    "        backtrack(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "\n",
    "        result = []\n",
    "\n",
    "        def generate(str,left,right):\n",
    "            if len(str) == 2*n:\n",
    "                result.append(str)\n",
    "                return\n",
    "            \n",
    "            if left < n:\n",
    "                generate(str+'(',left+1,right)\n",
    "            if right<left:\n",
    "                generate(str+')',left,right+1)\n",
    "\n",
    "        generate('',0,0)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans=[]\n",
    "        path=[]\n",
    "        def dfs(i,cnt) :\n",
    "            if i==2*n :\n",
    "                #print(path)\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if cnt<n :\n",
    "                path.append('(')\n",
    "                dfs(i+1,cnt+1)\n",
    "                path.pop()\n",
    "            if i-cnt<cnt :\n",
    "                path.append(')')\n",
    "                dfs(i+1,cnt)\n",
    "                path.pop()\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        \n",
    "        dp = [[\"\"] for i in range(0, n+1)]\n",
    "        dp[1] = [\"()\"]\n",
    "        \n",
    "        for i in range(2, n+1):\n",
    "            curr = []\n",
    "            for j in range(0, i):\n",
    "                select1 = dp[j]\n",
    "                select2 = dp[i-j-1]\n",
    "                for s1 in select1:\n",
    "                    for s2 in select2:\n",
    "                        if '(' + s1 + ')' + s2 not in curr:\n",
    "                            curr.append('(' + s1 + ')' + s2)\n",
    "                        if  s2 + '(' + s1 + ')' not in curr:\n",
    "                             curr.append(s2 + '(' + s1 + ')')\n",
    "            dp[i] = curr\n",
    "        return dp[n]\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n <= 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [\"()\"]\n",
    "        result = []\n",
    "        def backtrack(Curr, left, right):\n",
    "            if right == n:   #满足结束条件\n",
    "                result.append(''.join(Curr))\n",
    "                \n",
    "            if left < n:\n",
    "                Curr.append(\"(\")  #做出选择\n",
    "                backtrack(Curr, left + 1, right)  #路径，选择列表\n",
    "                Curr.pop() #撤销选择\n",
    "            if right < left:\n",
    "                Curr.append(\")\")\n",
    "                backtrack(Curr, left, right + 1)\n",
    "                Curr.pop()\n",
    "        backtrack([], 0, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        self.ans = []\n",
    "        def trackback(s,l,r):\n",
    "            if l+r == 2*n: self.ans.append(s)\n",
    "            if l<n: trackback(s+'(',l+1,r)\n",
    "            if r<l: trackback(s+')',l,r+1)\n",
    "        trackback('',0,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    \n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(left,right,path):\n",
    "            if left==0 and right==0:\n",
    "                res.append(path)\n",
    "                return\n",
    "            if left>0:\n",
    "                dfs(left-1,right,path+'(')\n",
    "            if right>left:\n",
    "                dfs(left,right-1,path+')')\n",
    "        res=[]\n",
    "        dfs(n,n,'')\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        self.ans = []\n",
    "        def recur(cur, left, right):\n",
    "            if len(cur) == 2 * n and left == right:\n",
    "                self.ans.append(cur)\n",
    "                return\n",
    "            if left < n:\n",
    "                recur(cur + \"(\", left + 1, right)\n",
    "            if right < left:\n",
    "                recur(cur + \")\", left, right + 1)\n",
    "            return\n",
    "        recur(\"\", 0, 0)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        ans = []\n",
    "        path = ['']* m\n",
    "        def dfs(i, k):\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if k < n:\n",
    "                path[i] = '('\n",
    "                dfs(i+1, k+1)\n",
    "            if i- k < k:\n",
    "                path[i] = ')'\n",
    "                dfs(i+1, k)\n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def func(s,a,b):\n",
    "            if(a==0 and b==0):\n",
    "                ansarr.append(s)\n",
    "                return\n",
    "            if(a!=0):\n",
    "                func(s+\"(\",a-1,b+1)\n",
    "            if(b!=0):\n",
    "                func(s+\")\",a,b-1)\n",
    "            return\n",
    "        ansarr = []\n",
    "        func(\"\",n,0)\n",
    "        return ansarr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(cur: str, l: int, r: int):\n",
    "            if l == 0 and r == 0:\n",
    "                ans.append(cur)\n",
    "                return\n",
    "            if l > 0:\n",
    "                dfs(cur + \"(\", l - 1, r)\n",
    "            if l < r:\n",
    "                dfs(cur + \")\", l, r - 1)\n",
    "        dfs(\"\", n, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        \n",
    "        dp = [[\"\"] for i in range(0, n+1)]\n",
    "        dp[1] = [\"()\"]\n",
    "        \n",
    "        for i in range(2, n+1):\n",
    "            curr = []\n",
    "            for j in range(0, i):\n",
    "                select1 = dp[j]\n",
    "                select2 = dp[i-j-1]\n",
    "                for s1 in select1:\n",
    "                    for s2 in select2:\n",
    "                        if '(' + s1 + ')' + s2 not in curr:\n",
    "                            curr.append('(' + s1 + ')' + s2)\n",
    "            dp[i] = curr\n",
    "        return dp[n]\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = {}\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            self.result[1] = ['()']\n",
    "            return ['()']\n",
    "        result = set()\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            for item in self.result.get(i, self.generateParenthesis(i)):\n",
    "                for item1 in self.result.get(n - i, self.generateParenthesis(n - i)):\n",
    "                    result.add(item + item1)\n",
    "                    result.add(item1 + item)\n",
    "        for item in self.result.get(n - 1, self.generateParenthesis(n - 1)):\n",
    "            result.add('({})'.format(item))\n",
    "        self.result[n] = list(result)\n",
    "        return self.result[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = {}\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            self.result[1] = ['()']\n",
    "            return ['()']\n",
    "        result = set()\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            for item in self.result.get(i, self.generateParenthesis(i)):\n",
    "                for item1 in self.result.get(n - i, self.generateParenthesis(n - i)):\n",
    "                    result.add(item + item1)\n",
    "                    result.add(item1 + item)\n",
    "        for item in self.result.get(n - 1, self.generateParenthesis(n - 1)):\n",
    "            result.add('({})'.format(item))\n",
    "        self.result[n] = list(result)\n",
    "        return self.result[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n <= 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [\"()\"]\n",
    "        result = []\n",
    "        def backtrack(Curr, left, right):\n",
    "            if right == n:   #满足结束条件\n",
    "                result.append(''.join(Curr))\n",
    "                \n",
    "            if left < n:\n",
    "                Curr.append(\"(\")  #做出选择\n",
    "                backtrack(Curr, left + 1, right)  #路径，选择列表\n",
    "                Curr.pop() #撤销选择\n",
    "            if right < left:\n",
    "                Curr.append(\")\")\n",
    "                backtrack(Curr, left, right + 1)\n",
    "                Curr.pop()\n",
    "        backtrack([], 0, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        self.res = []\n",
    "        seq = []\n",
    "        def dfs(left,right):\n",
    "            if len(seq) == 2 * n:\n",
    "                cur = \"\".join(seq)\n",
    "                self.res.append(cur)\n",
    "            \n",
    "            if left < n:\n",
    "                seq.append(\"(\")\n",
    "                dfs(left + 1,right)\n",
    "                seq.pop()\n",
    "            \n",
    "            if right < left:\n",
    "                seq.append(\")\")\n",
    "                dfs(left,right + 1)\n",
    "                seq.pop()\n",
    "        \n",
    "        dfs(0,0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n*2\n",
    "        ans = []\n",
    "        path = ['']*m\n",
    "        def dfs(i,left_number):\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "            if left_number < n:\n",
    "                path[i] = \"(\"\n",
    "                dfs(i+1,left_number+1)\n",
    "            if i - left_number < left_number:\n",
    "                path[i] = ')'\n",
    "                dfs(i+1, left_number)\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        \n",
    "        dp = [[\"\"] for i in range(0, n+1)]\n",
    "        dp[1] = [\"()\"]\n",
    "        \n",
    "        for i in range(2, n+1):\n",
    "            curr = []\n",
    "            for j in range(0, i):\n",
    "                select1 = dp[j]\n",
    "                select2 = dp[i-j-1]\n",
    "                for s1 in select1:\n",
    "                    for s2 in select2:\n",
    "                        if '(' + s1 + ')' + s2 not in curr:\n",
    "                            curr.append('(' + s1 + ')' + s2)\n",
    "            dp[i] = curr\n",
    "        return dp[n]\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        result = []\n",
    "        self.generate(n, n, \"\", result)\n",
    "        return result\n",
    "\n",
    "    def generate(self, left, right, s, result):\n",
    "        if left == 0 and right == 0:\n",
    "            result.append(s)\n",
    "            return\n",
    "        if left > 0:\n",
    "            self.generate(left - 1, right, s + \"(\", result)\n",
    "        if right > left:\n",
    "            self.generate(left, right - 1, s + \")\", result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = 2 * n\n",
    "        ans, path = [], ['' for _ in range(m)]\n",
    "\n",
    "        def dfs(i, open):\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if open < n:\n",
    "                path[i] = '('\n",
    "                dfs(i + 1, open + 1)\n",
    "            if i - open < open:\n",
    "                path[i] = ')'\n",
    "                dfs(i + 1, open)\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def helper(cur, l_count, r_count):\n",
    "            if l_count < n:\n",
    "                helper(cur+\"(\", l_count+1, r_count)\n",
    "            if r_count < n and r_count < l_count:\n",
    "                helper(cur+\")\", l_count, r_count+1)\n",
    "            if l_count == r_count == n:\n",
    "                ans.append(cur)\n",
    "                return \n",
    "\n",
    "        ans = []\n",
    "        helper(\"\", 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(s,right,left):\n",
    "            if len(s)==2*n:\n",
    "                ans.append(\"\".join(s))\n",
    "            if left<n:\n",
    "                s.append(\"(\")\n",
    "                dfs(s,right,left+1)\n",
    "                s.pop()\n",
    "            if right<left:\n",
    "                s.append(\")\")\n",
    "                dfs(s,right+1,left)\n",
    "                s.pop()\n",
    "        dfs([],0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def backtrack(S, left, right):\n",
    "            if len(S) == 2 * n:\n",
    "                ans.append(''.join(S))\n",
    "                return\n",
    "            if left < n:\n",
    "                S.append('(')\n",
    "                backtrack(S, left+1, right)\n",
    "                S.pop()\n",
    "            if right < left:\n",
    "                S.append(')')\n",
    "                backtrack(S, left, right+1)\n",
    "                S.pop()\n",
    "\n",
    "        backtrack([], 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 定义generate,递归,长度为n的是由n-1的+（ 或者+）构成\n",
    "# def valid 每次加上（ or ），检验（的个数-）的个数<0,直接返回False\n",
    "# 判断(的个数 和 )的个数是否为0\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def generate(A):\n",
    "            if len(A)==n*2:\n",
    "                # 判断是否已经满足长度，再判断是否合法\n",
    "                if valid(A):\n",
    "                    # 字符符合规范，进行拼接\n",
    "                    ans.append(''.join(A)) \n",
    "            else:\n",
    "                # 构造A\n",
    "                A.append('(')\n",
    "                generate(A)\n",
    "                A.pop() # 恢复原状\n",
    "\n",
    "                A.append(')')\n",
    "                generate(A)\n",
    "                A.pop() # 恢复原状\n",
    "\n",
    "        def valid(A):\n",
    "            tmp = 0\n",
    "            for i in A:\n",
    "                if i =='(':\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "                if tmp<0:\n",
    "                    return False\n",
    "            return tmp==0\n",
    "        # 调用两个函数\n",
    "        ans = []\n",
    "        generate([])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "\n",
    "        def dfs(n:int,path:string,open:int,close:int):\n",
    "            nonlocal ans\n",
    "            \n",
    "            if open>n or close>open:\n",
    "                return\n",
    "            \n",
    "            elif len(path)==n*2:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            \n",
    "            dfs(n,path+'(',open+1,close)\n",
    "            dfs(n,path+')',open,close+1)\n",
    "        path=[]\n",
    "        ans=[]\n",
    "        dfs(n,'',0,0)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        results = []\n",
    "        path = []\n",
    "        l = ['(', ')']\n",
    "        t = [0, 0]\n",
    "\n",
    "        def backtracking(t, n):\n",
    "            if len(path) == n*2:\n",
    "                results.append(''.join(path[:]))\n",
    "                return\n",
    "\n",
    "            for i in range(2):\n",
    "                if i == 1 and t[1] >= t[0]:\n",
    "                    continue\n",
    "                if t[i] >= n:\n",
    "                    continue\n",
    "                path.append(l[i])\n",
    "                t[i] += 1\n",
    "                backtracking(t, n)\n",
    "                path.pop(-1)\n",
    "                t[i] -= 1\n",
    "\n",
    "        backtracking(t, n)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 1: return [\"()\"]\n",
    "        res = []\n",
    "        def dfs(n, left, right, temp):\n",
    "            if left + right == 2 * n:\n",
    "                res.append(\"\".join(temp))\n",
    "                return\n",
    "            if left < n:\n",
    "                temp.append(\"(\")\n",
    "                dfs(n, left+1, right, temp)\n",
    "                temp.pop()\n",
    "            if right < left:\n",
    "                temp.append(\")\")\n",
    "                dfs(n, left, right+1, temp)\n",
    "                temp.pop()\n",
    "        \n",
    "        dfs(n, 0, 0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        self.backtrack(n, n)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self,left,right) -> None:\n",
    "        # 如果track中左括号数目小于右括号，则一定不合法\n",
    "        # left,right表示剩余左右括号\n",
    "        if left>right:\n",
    "            return\n",
    "        # 剩余左右括号小于零不合法\n",
    "        if left < 0 or right < 0:\n",
    "            return\n",
    "        # 找到答案 base case\n",
    "        if left == 0 and right==0:\n",
    "            self.res.append(\"\".join(self.track[:]))\n",
    "            return\n",
    "        # 做选择 递归 撤销选择\n",
    "        for ch in [\"(\",\")\"]:\n",
    "            self.track.append(ch)\n",
    "            if ch == \"(\":\n",
    "                self.backtrack(left-1,right)\n",
    "            elif ch == \")\":\n",
    "                self.backtrack(left,right-1)\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = {}\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            self.result[1] = ['()']\n",
    "            return ['()']\n",
    "        result = set()\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            for item in self.result.get(i, self.generateParenthesis(i)):\n",
    "                for item1 in self.result.get(n - i, self.generateParenthesis(n - i)):\n",
    "                    result.add(item + item1)\n",
    "                    result.add(item1 + item)\n",
    "        for item in self.result.get(n - 1, self.generateParenthesis(n - 1)):\n",
    "            result.add('({})'.format(item))\n",
    "        return list(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        if n <= 0:\n",
    "            return res\n",
    "        def dfs(path, l, r):\n",
    "            if len(path) == 2*n:\n",
    "                res.append(path)\n",
    "                return\n",
    "            if l < n:\n",
    "                dfs(path+'(', l+1, r)\n",
    "            if r < l:\n",
    "                dfs(path+')', l, r+1)\n",
    "        dfs(\"\", 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        # res = []\n",
    "        # string = \"\"\n",
    "\n",
    "        # def dfs(left, right, s):\n",
    "        #     nonlocal res\n",
    "        #     if right == 0 and left == 0:\n",
    "        #         res.append(s)\n",
    "        #         return\n",
    "        #     if left < 0 or right < 0 or right < left:\n",
    "        #         return\n",
    "        #     dfs(left - 1, right, s + \"(\")\n",
    "        #     dfs(left, right - 1, s + \")\")\n",
    "\n",
    "\n",
    "        # dfs(n, n, string)\n",
    "        # return res\n",
    "\n",
    "        ans = []\n",
    "        s = \"\"\n",
    "        def dfs(item, left, right):\n",
    "            if left == 0 and right == 0:\n",
    "                ans.append(item)\n",
    "            if left > 0:\n",
    "                dfs(item + \"(\", left - 1, right)\n",
    "            if left < right:\n",
    "                dfs(item + \")\", left, right - 1)\n",
    "\n",
    "        dfs(s, n, n)\n",
    "        \n",
    "        return ans \n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        string = \"\"\n",
    "        def dfs(left, right, s):\n",
    "            nonlocal res\n",
    "            if right == 0 and left == 0:\n",
    "                res.append(s)\n",
    "                return\n",
    "            if left < 0 or right < 0 or right < left:\n",
    "                return\n",
    "            dfs(left - 1, right, s + \"(\")\n",
    "            dfs(left, right - 1, s + \")\")\n",
    "\n",
    "\n",
    "        dfs(n, n, string)\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def transfer(sefl,path):\n",
    "        res =\"\"\n",
    "        for p in path:\n",
    "            if p==0:\n",
    "                res = res+\"(\"\n",
    "            else:\n",
    "                res =res+\")\"\n",
    "        return res\n",
    "\n",
    "    def traceBack(self,n,path,res):\n",
    "        if sum(path)>n:\n",
    "            return\n",
    "        if sum(path)>len(path)//2:\n",
    "            return \n",
    "\n",
    "        if len(path)>n and sum(path)==0:\n",
    "            return\n",
    "        if len(path)==2*n:\n",
    "            if sum(path)==n:\n",
    "                res.append(self.transfer(path))\n",
    "                return\n",
    "            else:\n",
    "                return\n",
    "        for ch in [0,1]:\n",
    "            path.append(ch)\n",
    "            self.traceBack(n,path,res)\n",
    "            path.pop()\n",
    "\n",
    "        return \n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        path=list()\n",
    "        res = list()\n",
    "        self.traceBack(n,path,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        ans = []\n",
    "        path = [''] * m\n",
    "        def dfs(i: int, open: int) -> None:\n",
    "            if i == m and open==i-open:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if open < n:  # 可以填左括号\n",
    "                path[i] = '('\n",
    "                dfs(i + 1, open + 1)\n",
    "            if i - open < open:  # 可以填右括号\n",
    "                path[i] = ')'\n",
    "                dfs(i + 1, open)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        dp = [[] for i in range(n + 1)]\n",
    "        dp[1] = ['()']\n",
    "        unionSet = set()\n",
    "        unionSet.add('()')\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            for j in dp[i - 1]:\n",
    "                for k in range(len(j)):\n",
    "                    if j[k] == '(':\n",
    "                        tmp1 = f'{j[:k+1]}(){j[k + 1:]}'\n",
    "                        if tmp1 not in unionSet:\n",
    "                            unionSet.add(tmp1)\n",
    "                            dp[i].append(tmp1)\n",
    "\n",
    "                tmp2 = f'({j})' \n",
    "                if tmp2 not in unionSet:\n",
    "                    dp[i].append(tmp2)\n",
    "                    unionSet.add(tmp2)\n",
    "\n",
    "                tmp3 = f'(){j}'\n",
    "                if tmp3 not in unionSet:\n",
    "                    unionSet.add(tmp3)\n",
    "                    dp[i].append(tmp3)\n",
    "\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = {}\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            self.result[1] = ['()']\n",
    "            return ['()']\n",
    "        result = set()\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            for item in self.result.get(i, self.generateParenthesis(i)):\n",
    "                for item1 in self.result.get(n - i, self.generateParenthesis(n - i)):\n",
    "                    result.add(item + item1)\n",
    "                    result.add(item1 + item)\n",
    "        for item in self.result.get(n - 1, self.generateParenthesis(n - 1)):\n",
    "            result.add('({})'.format(item))\n",
    "        return list(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        track = []\n",
    "        def backtrack(left, right, n):\n",
    "            if left==n and right==n:\n",
    "                res.append(''.join(track))\n",
    "                return\n",
    "            if left > n or right>n or right > left:\n",
    "                return\n",
    "            \n",
    "            for c in ['(', ')']:\n",
    "                track.append(c)\n",
    "                if c=='(':\n",
    "                    backtrack(left+1, right, n)\n",
    "                else:\n",
    "                    backtrack(left, right+1, n)\n",
    "                track.pop(-1)\n",
    "        backtrack(0, 0, n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = {}\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            self.result[1] = ['()']\n",
    "            return ['()']\n",
    "        result = set()\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            for item in self.result.get(i, self.generateParenthesis(i)):\n",
    "                for item1 in self.result.get(n - i, self.generateParenthesis(n - i)):\n",
    "                    result.add(item + item1)\n",
    "                    result.add(item1 + item)\n",
    "        for item in self.result.get(n - 1, self.generateParenthesis(n - 1)):\n",
    "            result.add('({})'.format(item))\n",
    "        return list(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def backup(left, right, cur):\n",
    "            if left + right == n * 2:\n",
    "                ans.append(cur)\n",
    "                return\n",
    "            if left < n:\n",
    "                left += 1\n",
    "                cur += '('\n",
    "                backup(left, right, cur)\n",
    "                left -= 1\n",
    "                cur = cur[:-1]\n",
    "            if right < left:\n",
    "                right += 1\n",
    "                cur += ')'\n",
    "                backup(left, right, cur)\n",
    "            return\n",
    "        backup(0, 0, \"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        path = []\n",
    "        result = []\n",
    "\n",
    "        def dfs(left, right):\n",
    "            if left == 0 and right == 0:\n",
    "                result.append(''.join(path[:]))\n",
    "                return \n",
    "            if left > right:\n",
    "                return  \n",
    "            if left > 0:\n",
    "                path.append('(')\n",
    "                dfs(left - 1, right)\n",
    "                path.pop() \n",
    "            if right > 0:\n",
    "                path.append(')')\n",
    "                dfs(left, right - 1)\n",
    "                path.pop() \n",
    "        \n",
    "        dfs(n, n) \n",
    "        return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        \n",
    "        def match(path):\n",
    "            stack = []\n",
    "            for i in path:\n",
    "                if i =='(':\n",
    "                    stack.append(i)\n",
    "                if i == ')':\n",
    "                    if len(stack) == 0:\n",
    "                        return False\n",
    "                    else:\n",
    "                        stack.pop()\n",
    "            \n",
    "            if len(stack) > 0:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "\n",
    "        # 生成得到匹配的括号\n",
    "     \n",
    "        \n",
    "        def backtracking():\n",
    "            count = path.count(')')\n",
    "            count1 = len(path) - count\n",
    "\n",
    "            if len(path) == n*2:\n",
    "                if count == count1:\n",
    "                    if match(path):\n",
    "                        if ''.join(path[:]) not in final_path:\n",
    "                            final_path.append(''.join(path[:])) #添加新的\n",
    "                return \n",
    "\n",
    "          \n",
    "            \n",
    "            if (n-count1)< 0 or (n-count)<0  or count1 < count:\n",
    "                return \n",
    "           \n",
    "            for i in ['(',')']:\n",
    "              \n",
    "                path.append(i)\n",
    "                backtracking()\n",
    "                path.pop()\n",
    "                   \n",
    "            \n",
    "        # kuohao = ['(' for _ in range(n)] + [')' for _ in range(n)]\n",
    "    \n",
    "        path = []\n",
    "        final_path = []\n",
    "        backtracking()\n",
    "        return final_path\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = {}\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 1:\n",
    "            self.result[1] = ['()']\n",
    "            return ['()']\n",
    "        result = set()\n",
    "        for i in range(1, n // 2 + 1):\n",
    "            for item in self.result.get(i, self.generateParenthesis(i)):\n",
    "                for item1 in self.result.get(n - i, self.generateParenthesis(n - i)):\n",
    "                    result.add(item + item1)\n",
    "                    result.add(item1 + item)\n",
    "        for item in self.result.get(n - 1, self.generateParenthesis(n - 1)):\n",
    "            result.add('({})'.format(item))\n",
    "        self.result[n] = list(result)\n",
    "        return self.result[n]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
